Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1,
compute how much water it is able to trap after raining.
For example,

• Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

题目大意：给定n个整数代表木板的长度（宽度为1），木板水平方向依次放置，求容纳水的体积

题目难度：Hard

/**
 * Created by gzdaijie on 16/5/21
 * 水桶效应,容量与第二长的木板有关
 * 比较首末木板的长度,从较小的木板smaller开始计算sum,直到遇到比smaller大的木板
 * 遇到比smaller更大的木板,更新smaller,重复上一个步骤
 * 时间O(N), O(1)
 * 例如1,0,4,2,5,0,3
 * 计算过程 1->0->4（sum=1）-> 3->0->5(sum=4)->4->2->5(sum=6)
 */
public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 2) return 0;
        int start = 0 , end = height.length - 1;
        int sum = 0;

        while (start <= end) {
            if (height[start] < height[end]) {
                int smaller = height[start++];
                while (start < end && height[start] <= smaller) {
                    sum += smaller - height[start];
                    start++;
                }
            } else {
                int smaller = height[end--];
                while (start < end && height[end] <= smaller) {
                    sum += smaller - height[end];
                    end--;
                }
            }
        }
        return sum;
    }
}